// Created by WXX on 2021/10/22 19:47
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 动态规划
class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int f = nums[0], res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            f = max(f, 0) + nums[i];
            res = max(res, f);
        }
        return res;
    }
};

int main() {

    vector<int> nums = {2, -1, -3, 4, -1, 2, 1, -5, 4};
    cout << Solution().maxSubArray(nums) << endl;

    return 0;
}
